package datastructure;

class MaxHeap {
	private int[] array;

	private int size;

	public void maxHeapSort(int[] a) {
		array = a;
		size = array.length - 1;
		heapSort();
	}

	private void heapSort() {
		buildMaxHeap();
		for (int i = size; i > 1; i--) {
			swap(1, i);
			size--;
			maxHeapify(1);
		}
	}

	private void swap(int i, int j) {
		array[i] ^= array[j];
		array[j] ^= array[i];
		array[i] ^= array[j];
	}

	private void maxHeapify(int i) {
		int l = i << 1;
		int r = l + 1;
		int max = i;
		if (l <= size && array[l] > array[i])
			max = l;
		if (r <= size && array[r] > array[max])
			max = r;
		if (max != i) {
			swap(i, max);
			maxHeapify(max);
		}
	}

	private void buildMaxHeap() {
		for (int i = size / 2; i > 0; i--)
			maxHeapify(i);
	}

	public void init(int s) {
		size = 1;
		array = new int[s + 1];
	}

	public void insert(int value) {
		int i = size;
		int p = i >> 1;
		array[size++] = value;
		while (i > 1 && array[p] < array[i]) {
			swap(i, p);
			i = p;
			p = i >> 1;
		}
	}

	public int peek() {
		return array[1];
	}

	public int poll() {
		int p = array[1];
		array[1] = array[--size];
		maxHeapify(1);
		return p;
	}
}
